package org.apache.commons.graph.algorithms.spanning

import com.gitee.wsl.ext.set.pollFirst
import org.apache.commons.graph.Graph

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * A [SuperVertex] is a collection of vertex objects and is only
 * used internally by Boruvka's algorithm to find a minimum spanning tree.
 *
 * @param <V>  the Graph vertices type
 * @param <W>  the weight type
 * @param <WE> the Graph weighted edges type
 * @param <G>  the input Graph type
 * @param <WC> the weight operations
</WC></G></WE></W></V> */
internal class SuperVertex<V, W, WE>(
    source: V,
    /** The reference to the graph.  */
    private val graph: Graph<V, WE>,
    weightComparator: WeightedEdgesComparator<W, WE>
) : Iterable<V> {

    /** The set of vertices combined in this [SuperVertex].  */
    private val vertices: MutableSet<V> = HashSet()

    /** The ordered set of edges to other [SuperVertex] objects.  */
    private val orderedEdges: MutableSet<WE>

    /**
     * Create a new [SuperVertex] instance with `source`
     * as start vertex.
     *
     * @param source the start vertex
     * @param graph the underlying graph
     * @param weightComparator the comparator used to sort the weighted edges
     */
    init {
        vertices.add(source)
        orderedEdges = sortedSetOf(weightComparator)
        //orderedEdges = TreeSet(weightComparator)

        // add all edges for this vertex to the sorted set
        for (w in graph.getConnectedVertices(source)) {
            val edge = graph.getEdge(source, w)!!
            orderedEdges.add(edge)
        }
    }

    /**
     * Returns the edge with the minimum weight to other [SuperVertex]
     * instances.
     *
     * @return the minimum weight edge or `null` if there is no edge
     */
    val minimumWeightEdge: WE?
        get() {
            var found = false
            var edge: WE? = null
            while (!found && orderedEdges.isNotEmpty()) {
                edge = orderedEdges.pollFirst()
                val pair = graph.getVertices(edge)
                if (!vertices.contains(pair!!.head) || !vertices.contains(pair.tail)) {
                    found = true
                }
            }
            return edge
        }

    /** {@inheritDoc}  */
    override fun iterator(): MutableIterator<V> {
        return vertices.iterator()
    }

    /**
     * Merges another [SuperVertex] instance into this one.
     * The edges from the other [SuperVertex] are only added in case
     * they are not to vertices already contained in this [SuperVertex].
     *
     * @param other the [SuperVertex] to be merged into this
     */
    fun merge(other: SuperVertex<V, W, WE>) {
        for (v in other.vertices) {
            vertices.add(v)
        }

        for (edge in other.orderedEdges) {
            val pair = graph.getVertices(edge)
            if (!vertices.contains(pair!!.head) || !vertices.contains(pair.tail)) {
                orderedEdges.add(edge)
            }
        }
    }
}
